package me.mingshan.leetcode;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/product-of-array-except-self/
 *
 * 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
 *
 * 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
 *
 * 请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums = [1,2,3,4]
 * 输出: [24,12,8,6]
 * 示例 2:
 *
 * 输入: nums = [-1,1,0,-3,3]
 * 输出: [0,0,9,0,0]
 *
 *
 * @author hanjuntao
 * @date 2025/7/21 0021
 */
public class L_238_product_of_array_except_self {

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        int[] result = productExceptSelf2(nums);
        System.out.println(Arrays.toString(result));
        // [24, 12, 8, 6]
    }

    /**
     * 思路：
     *
     * 暴力解法
     *
     * 两层循环，暴力计算出乘积
     *
     * @param nums
     * @return
     */
    public static int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i != j) {
                    if (result[i] == 0) {
                        result[i] = nums[j];
                    } else {
                        result[i] = result[i] * nums[j];
                    }
                }
            }
        }

        return result;
    }

    /**
     * 思路：
     *
     * 上述可以转换为山峰问题，要获取一个数除自身外其他数的乘积，拆分两部分，左边数的乘积 * 右边数的乘积
     *
     * 左边数的乘积 和 右边数的乘积可以提前算出来，
     *
     * 时间复杂度：O(N)
     * 空间复杂度：O(N)
     *
     *
     *
     * @param nums
     * @return
     */
    public static int[] productExceptSelf2(int[] nums) {
        int[] result = new int[nums.length];

        int[] left = new int[nums.length];
        int[] right = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            left[i] = i == 0 ? nums[i] : left[i - 1] * nums[i];
        }

        for (int i = nums.length - 1; i >= 0; i--) {
            right[i] = i == nums.length - 1 ? nums[i] : right[i + 1] * nums[i];
        }

        for (int i = 0; i < nums.length; i++) {
            if (i == 0) {
                result[i] = right[i + 1];
            } else if (i == nums.length - 1) {
                result[i] = left[i - 1];
            } else {
                result[i] = left[i - 1] * right[i + 1];
            }
        }

        return result;
    }
}
